/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    //计算链表长度
    int getListSize(ListNode* head)
    {
        int count = 0;
        while(head) {
            head = head->next;
            count++;
        }
        return count;
    }

    //在链表头部插入元素，返回插入后的链表头指针
    ListNode* addHead(ListNode* head, ListNode* Node)
    {
        Node->next = head;
        return Node;
    }

    ListNode* reverseKGroup(ListNode* head, int k)
    {
        int length = getListSize(head);
        ListNode tmpHead(-1);
        ListNode* pNode = &tmpHead;
        while(length >= k) {
            ListNode* pHead = NULL;
            for(int i = 0; i < k; i++) {
                ListNode* ptmpNode = head;
                head = head->next;
                ptmpNode->next = NULL;
                //透过头插法构建反序的临时链表
                pHead = addHead(pHead, ptmpNode);
            }
            pNode->next = pHead;
            while(pNode->next)
                pNode = pNode->next;
            length -= k;
        }
        //将链表剩余元素插入结果链表的尾部
        pNode->next = head;
        return tmpHead.next;
    }
};
